/**
 * @param {number[]} nums
 * @return {number}
 */
// 推荐使用这个 ai 的回答的答案
/* 
为了求解环形数组中的最大子数组和，可以将问题分解为两种情况：不跨越环形边界的子数组和跨越环形边界的子数组。
对于前者，可以直接使用 Kadane 算法；对于后者，可以通过计算数组总和减去最小子数组和来得到。

方法思路
情况一：非环形子数组：直接使用 Kadane 算法计算最大子数组和。
情况二：环形子数组：计算数组的总和total，并使用 Kadane 算法计算最小子数组和。环形子数组的最大和为total - 最小子数组和。
特殊情况处理：如果所有元素都是负数，情况二的结果会是 0（即不选任何元素），但题目要求子数组至少包含一个元素，因此此时应返回情况一的结果。
*/
var maxSubarraySumCircular = function (nums) {
  // 初始化最大子数组和（非环形情况）
  let currentMax = nums[0]; // 以当前元素结尾的最大子数组和
  let globalMax = nums[0]; // 全局最大子数组和

  // 初始化最小子数组和（用于计算环形情况）
  let currentMin = nums[0]; // 以当前元素结尾的最小子数组和
  let globalMin = nums[0]; // 全局最小子数组和

  // 数组总和，用于计算环形子数组的可能和
  let total = nums[0];

  // 遍历数组，同时计算最大子数组和、最小子数组和、数组总和
  for (let i = 1; i < nums.length; i++) {
    // 更新最大子数组和：选择加入当前元素或重新开始
    currentMax = Math.max(nums[i], currentMax + nums[i]);
    globalMax = Math.max(globalMax, currentMax);

    // 更新最小子数组和：选择加入当前元素或重新开始
    currentMin = Math.min(nums[i], currentMin + nums[i]);
    globalMin = Math.min(globalMin, currentMin);

    // 累加数组总和
    total += nums[i];
  }

  // 处理所有元素均为负数的特殊情况
  // 此时total === globalMin，环形最大和即为非环形的globalMax（至少选一个元素）
  if (total === globalMin) {
    return globalMax;
  }

  // 返回两种情况的较大值：
  // 1. 非环形的最大子数组和（globalMax）
  // 2. 环形情况：数组总和减去最小子数组和（total - globalMin）
  return Math.max(globalMax, total - globalMin);
};

var maxSubarraySumCircular = function (nums) {
  let maxS = Number.MIN_SAFE_INTEGER; // 最大子数组和，不能为空
  let minS = 0; // 最小子数组和，可以为空
  let maxF = 0, minF = 0, sum = 0;
  for (const x of nums) {
    // 以 nums[i-1] 结尾的子数组选或不选（取 max）+ x = 以 x 结尾的最大子数组和
    maxF = Math.max(maxF, 0) + x;
    maxS = Math.max(maxS, maxF);
    // 以 nums[i-1] 结尾的子数组选或不选（取 min）+ x = 以 x 结尾的最小子数组和
    minF = Math.min(minF, 0) + x;
    minS = Math.min(minS, minF);
    sum += x;
  }
  return sum === minS ? maxS : Math.max(maxS, sum - minS);
};


/**
 * @param {number[]} nums
 * @return {number}
 */
// 这个是非 kadane 算法，就是使用普通的算法，思路比较简单但是算法的复杂度比较高
/* 
如果不使用 Kadane 算法，可以通过枚举所有可能的子数组来求解环形数组的最大和。
这种方法虽然时间复杂度较高（O (n²)），但逻辑直观，容易理解和记忆。

方法思路
处理普通子数组：直接遍历所有可能的连续子数组，计算其最大和。
处理环形子数组：将数组复制一份接在原数组后面，形成长度为 2n 的新数组。枚举所有长度不超过 n 的子数组，计算其最大和。
返回最大值：比较普通子数组和环形子数组的最大和，取较大值。
*/
var maxSubarraySumCircular = function (nums) {
  const n = nums.length;
  let maxSum = -Infinity;

  // 处理普通子数组
  for (let i = 0; i < n; i++) {
    let currentSum = 0;
    for (let j = i; j < n; j++) {
      currentSum += nums[j];
      maxSum = Math.max(maxSum, currentSum);
    }
  }

  // 处理环形子数组
  const extendedNums = [...nums, ...nums]; // 复制数组
  for (let i = 0; i < n; i++) {
    let currentSum = 0;
    for (let j = i; j < i + n; j++) {
      currentSum += extendedNums[j];
      maxSum = Math.max(maxSum, currentSum);
    }
  }

  return maxSum;
};